前言

嘿嘿～今天我們要來挑戰一個有趣的設計題目！你是否曾經想過，要設計一個特別的堆疊，不僅能執行一般的 push 和 pop 操作，還能在 O(1) 時間內快速找到最小值？

這就是今天的任務啦！
來，我們要打造一個 Min Stack，這個神奇的堆疊不但能記錄數字，還能隨時幫我們找到當前堆疊中的最小值，是不是很酷？
讓我們來看看要怎麼完成這個設計挑戰吧！😄

題目 Min Stack

難度：Medium

題目描述：

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

設計一個支持 push、pop、top 和在常數時間內檢索最小元素的堆疊。
實作 MinStack 類別：

• MinStack() 初始化堆疊物件。
• void push(int val) 將元素 val 推入堆疊。
• void pop() 移除堆疊頂部的元素。
• int top() 獲取堆疊頂部的元素。
• int getMin() 檢索堆疊中的最小元素。

必須以 O(1) 時間複雜度實現這些功能。

接下來我們會詳細解析如何使用堆疊法來解決這個問題，並提供具體的實作步驟～準備好了嗎？
Let's go！

解法思路

為了達到 O(1) 時間內取得最小值，我們需要使用兩個堆疊：

1. 主堆疊：用來正常存放每次 push 進來的元素。
2. 輔助堆疊：用來追蹤當前的最小值。當我們執行 push 操作時，不僅要將元素壓入主堆疊，還要在輔助堆疊中壓入當前的最小值；當執行 pop 操作時，兩個堆疊同時彈出對應元素。

這樣，我們每次 push 或 pop 操作後，輔助堆疊的頂部元素就始終保持堆疊中的最小值，從而能夠在 O(1) 的時間內完成 getMin 操作。

詳細步驟

1. push(val)：將 val 壓入主堆疊。同時，如果輔助堆疊為空或者 val 小於等於輔助堆疊的頂部元素，就將 val 壓入輔助堆疊。這樣，我們確保輔助堆疊中的元素始終是當前堆疊的最小值。

2. pop()：將主堆疊的頂部元素彈出。如果輔助堆疊的頂部元素等於主堆疊彈出的元素，輔助堆疊也同步彈出。這樣確保輔助堆疊依然保存的是剩下元素中的最小值。

3. top()：返回主堆疊的頂部元素。

4. getMin()：直接返回輔助堆疊的頂部元素，這個元素就是當前堆疊中的最小值。

實作

class MinStack {
    private stack: number[];
    private minStack: number[];

    constructor() {
        this.stack = [];      // 主堆疊
        this.minStack = [];   // 輔助堆疊
    }

    // 將元素 val 壓入堆疊
    push(val: number): void {
        this.stack.push(val);
        // 如果輔助堆疊為空，或當前元素比輔助堆疊頂部元素小或等於，壓入輔助堆疊
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    // 將頂部元素彈出
    pop(): void {
        const poppedValue = this.stack.pop();
        // 如果彈出的值等於輔助堆疊的頂部元素，輔助堆疊也同步彈出
        if (poppedValue === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }

    // 獲取堆疊的頂部元素
    top(): number {
        return this.stack[this.stack.length - 1];
    }

    // 獲取堆疊中的最小值
    getMin(): number {
        return this.minStack[this.minStack.length - 1];
    }
}

解題心法

1. 輔助堆疊的作用：

   • 輔助堆疊專門用來保存最小值，每次有新元素壓入時，我們比較新元素與輔助堆疊的頂部元素，確保最小的元素始終在輔助堆疊的頂部。這樣我們可以在 O(1) 的時間內取得最小值，而不需要每次重新遍歷主堆疊。

2. 同步操作：

   • 當主堆疊 pop() 時，如果被彈出的元素恰好是當前最小值，我們也同步從輔助堆疊中彈出最小值。這樣我們的輔助堆疊可以始終保持正確的最小值狀態。

3. 時間與空間複雜度：

   • 時間複雜度：所有操作 (push、pop、top、getMin) 都是 O(1)，因為我們通過輔助堆疊實現了在常數時間內檢索最小值。
   • 空間複雜度：O(n)，需要額外的輔助堆疊來存儲最小值，最壞情況下輔助堆疊與主堆疊的大小相等。

題型的方法比較

1. 堆疊法：

• 適合用於需要追蹤堆疊中數據狀態的情況，比如最小值、最大值等。像這道 Min Stack 題目，我們就利用了堆疊法來解決追蹤最小值的問題。

2. 動態規劃法：

• 適合解決有狀態遞迴關係的問題，比如之前的 Longest Valid Parentheses 題目，使用 dp 陣列來記錄每一步的最優解。

3. 雙指針法：

• 適合用於遍歷並且雙向掃描的問題，像我們在處理有效括號長度時，使用雙指針來同時從兩端進行掃描。

總結

這道 Min Stack 題目是典型的堆疊設計問題，我們通過使用輔助堆疊來保持最小值，從而能夠以 O(1) 的時間完成 getMin 操作。這是解決數據追蹤問題中常見且高效的方法。

如果你喜歡這種解題方式，還可以繼續挑戰更多類似的堆疊題目哦！